package com.example.demo.Calss18_dongtaiguihua;

/**
 * @program: java_base
 * @description: 动态规划
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/03 15:04
 */
public class Code02_CardsInLineDemo {
    /**
     * 给定一个整型数组arr代表数值不同的纸牌,
     * 排成一条线
     * 玩家A和玩家B依次拿走每一张牌
     * 规定玩家A先拿
     * 玩家B后拿
     * 但每个玩家每次只能拿最左或者最右的牌
     * 玩家A和玩家B智商一样请返回最后获胜者的分数
     *
     * 数组情况eg：[100,3]
     * 先手会拿100
     * 此时后手只能拿走3
     */


    public int win1(int[] arr){
        if (arr == null || arr.length== 0) {
            return 0;
        }
        int first = xian1(arr, 0, arr.length - 1);
        int second = hou1(arr, 0, arr.length - 1);
        return first > second ? 1 : 2;
    }
    /**
     * 函数作用：此时，对手挑选完成后，自己全力以赴挑选最大的！
     * @param arr 总牌
     * @param L   可以拿到最左边
     * @param R   可以拿到最右边
     * @return
     */
    public int xian1(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }

        int ans1 = arr[L] + hou1(arr, L + 1, R);
        int ans2 = arr[R] + hou1(arr, L, R - 1);

        return Math.max(ans1, ans2);

    }

    /**
     * 函数作用：此时，对手先挑选，留给后手的最坏选择
     * [L,R] 后手获得最好分数
     * 全都是先手预定好的方式进行。
     * 这个是先手给后手留的 min
     * @param arr
     * @param L 先手拿的时候的L
     * @param R 先手拿的时候的R
     * @return
     */
    // 后手是看着 先手拿走，这个情况
    public int hou1(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        // 对手那走了L的数，自己能获得的最大值。
        // 剩下的最优
        int i = xian1(arr, L + 1, R);
        // 对手那走了R的数，自己能获得的最大值。
        // 剩下的最优
        int i1 = xian1(arr, L, R - 1);
        // 这个是先手给后手留的 min。这个是先手留下的决定，
        // 先手能获得 这两个的最小值。
        // 先手每次都会这么去给后手留 min，而不是max
        // 对手是算好的，剩下的最优给你的
        return Math.min(i, i1);
    }


}
